package com.ztom.daily.n2022.m4;

/**
 * 二进制表示中质数个计算置位
 * <p>
 * https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/
 *
 * @author ZhangTao
 */
public class Day05CountPrimeSetBits {

    public int countPrimeSetBits(int left, int right) {
        if (left > right) {
            return 0;
        }

        int res = 0;
        for (int i = left; i <= right; i++) {
            if (judge(i)) {
                res++;
            }
        }
        return res;
    }

    private boolean judge(int num) {
        int tmp = num;
        int mostRight = 0;
        int res = 0;
        while (tmp > 0) {
            mostRight = tmp & -tmp;
            if (mostRight != 0) {
                res++;
                tmp -= mostRight;
            }
        }
        return isPrime(res);
    }

    private boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if ((num % i) == 0) {
                return false;
            }
        }
        return true;
    }
}
